﻿#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <ratio>
#include<vector>
#include<map>
using namespace std;
#if 0
namespace 前缀和
{
    int main()
    {
        int n, q; cin >> n >> q;
        vector<int> arr(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            cin >> arr[i];
        }
        int l, r;
        vector<long long int> dp(n + 1, 0);//防溢出
        for (int i = 1; i <= n; i++)
        {
            dp[i] = dp[i - 1] + arr[i];
        }
        while (q--)
        {
            cin >> l >> r;
            cout << dp[r] - dp[l - 1] << endl;
        }

        return 0;
    }
}
namespace 二维前缀和
{
#include <iostream>
#include<vector>
    using namespace std;

    int main()
    {
        int n, m, q; cin >> n >> m >> q;
        vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cin >> arr[i][j];
            }
        }
        vector<vector<long long int>> dp(n + 1, vector<long long int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                    - dp[i - 1][j - 1] + arr[i][j];
            }
        }
        int x1, y1, x2, y2;
        while (q--)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
        }
        return 0;

    }
    // 64 位输出请用 printf("%lld")
}

namespace cf
{
#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
    using namespace std;
    int main()
    {
        int t; cin >> t;
        while (t--)
        {
            int n, q; cin >> n >> q;
            string a; string b; cin >> a >> b;
            string c = " " + a;
            string d = " " + b;
            //存储的是从1到r区间每个字符出现的个数
            vector<vector<int>> dpc(n + 1, vector<int>(26, 0));
            vector<vector<int>> dpd(n + 1, vector<int>(26, 0));
            //初始化前缀和数组
            for (int i = 1; i <= n; i++)
            {
                for (char j = 'a'; j <= 'z'; j++)
                {
                    //当前位置的每个位置出现的字符个数等于上一个位置出现的加上当前位值字符个数
                    dpc[i][j - 'a'] = dpc[i - 1][j - 'a'] + (c[i] == j ? 1 : 0);
                    dpd[i][j - 'a'] = dpd[i - 1][j - 'a'] + (d[i] == j ? 1 : 0);
                }
            }
            int l, r;
            while (q--)
            {
                cin >> l >> r;
                int ret = 0;
                //处理c字符串每个区间中每个字符个数
                int arr1[26] = { 0 };
                //处理d字符串每个区间中字符个数
                int arr2[26] = { 0 };
                //每次询问使用我们的dp表
                for (char a = 'a'; a <= 'z'; a++)
                {
                    arr1[a - 'a'] = dpc[r][a - 'a'] - dpc[l - 1][a - 'a'];
                    arr2[a - 'a'] = dpd[r][a - 'a'] - dpd[l - 1][a - 'a'];
                    ret += abs(arr1[a - 'a'] - arr2[a - 'a']);
                }
                cout << ret / 2 << endl;
            }
        }
        return 0;
    }
}
namespace 寻找数组的中心下标
{
    class Solution
    {
    public:
        int pivotIndex(vector<int>& nums)
        {
            int n = nums.size() - 1;
            vector<int> g(n + 1, 0), f(n + 1, 0);
            f[0] = 0; g[n] = 0;
            for (int i = 1; i <= n; i++)
            {
                f[i] = f[i - 1] + nums[i - 1];
            }
            for (int i = n - 1; i >= 0; i--)
            {
                g[i] = g[i + 1] + nums[i + 1];
            }
            for (int i = 0; i <= n; i++)
            {
                if (f[i] == g[i]) return i;
            }
            return -1;
        }
    };
}
namespace 除自身之外数组的乘积
{
    class Solution
    {
    public:
        vector<int> productExceptSelf(vector<int>& nums)
        {
            int n = nums.size();
            vector<int> f(n), g(n), ret(n);
            f[0] = 1; g[n - 1] = 1;
            for (int i = 1; i < n; i++)
            {
                f[i] = f[i - 1] * nums[i - 1];
            }
            for (int i = n - 2; i >= 0; i--)
            {
                g[i] = g[i + 1] * nums[i + 1];
            }
            for (int i = 0; i < n; i++)
            {
                ret[i] = f[i] * g[i];
            }
            return ret;
        }
    };
}
namespace 和尾k的子数组
{
    class Solution
    {
    public:
        int subarraySum(vector<int>& nums, int k)
        {
            int n = nums.size();
            map<int, int>haxi;
            int sum = 0, ret = 0;
            haxi[0] = 1;//处理sum==k的情况此时的前缀和等于0
            for (int i = 0; i < n; i++)
            {
                sum += nums[i];
                //如果哈希表中出现sum-k的次数大于0
                if (haxi.count(sum - k)) ret += haxi[sum - k];
                haxi[sum]++;
            }
            return ret;
        }
    };
}
namespace  和可被K整除的子数组
{
    class Solution
    {
    public:
        int subarraysDivByK(vector<int>& nums, int k)
        {
            map<int, int> haxi;
            int ret = 0, sum = 0;
            haxi[0] = 1;//余数为0一定有一个
            for (int i = 0; i < nums.size(); i++)
            {
                sum += nums[i];
                int r = (sum % k + k) % k;
                if (haxi.count(r)) ret += haxi[r];
                haxi[r]++;
            }
            return ret;
        }
    };
}
#endif
namespace 连续数组
{
    class Solution
    {
    public:
        int findMaxLength(vector<int>& nums)
        {
            int n = nums.size();

            int ret = INT_MIN; map<int, int> haxi; haxi[0] = -1;//哈希表存放的是下标
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += nums[i] == 0 ? -1 : 1;
                //如果有用前面的
                if (haxi.count(sum)) ret = max(ret, i - haxi[sum]);
                else haxi[sum] = i;
            }
            return ret;
        }
    };
}
namespace 矩形区域和
{
    class Solution
    {
    public:
        vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
        {
            int m = mat.size();
            int n = mat[0].size();
            vector<vector<int>> ret(m, vector<int>(n));
            //用二维前缀和来解决
            vector<vector<int>> dp(m + 1, vector<int>(n + 1));
            //多开一个也就是说原数组的下标对应我的dp表的加一位置
            //初始化dp表
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
                }
            }
            //使用我们的dp表
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    int x1 = i - k < 0 ? 0 : i - k;
                    int y1 = j - k < 0 ? 0 : j - k;
                    int x2 = i + k > m - 1 ? m - 1 : i + k;
                    int y2 = j + k > n - 1 ? n - 1 : j + k;
                    ret[i][j] = dp[x2 + 1][y2 + 1] - dp[x2 + 1][y1] - dp[x1][y2 + 1] + dp[x1][y1];
                }
            }
            return ret;
        }
    };
}

//int main()
//{
//    vector<int> a({ 1,1,0,0,1,1,0,1 });
//    判断字符是否唯一::Solution().isUnique("abc");
//    return 0;
//}
